#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010; //输入字符串个数的上限
const int M = 20;   //字符串长度的上限

int n, m, l;
char a[N][M], b[M];
int f[M][M]; //最短编辑距离的状态表示
int res;
int la, lb; //存储当前字符串的长度

int main()
{
    freopen("cin.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) //输入n个待转换序列
        cin >> a[i] + 1;
    while (m--) //m次询问
    {
        res = 0;                    //现阶段符合的为0
        cin >> b + 1 >> l;          //输入目标字符串以及步数限制
        for (int i = 0; i < n; ++i) //遍历所有待转换字符串
        {
            memset(f, 0, sizeof f); //每次记得初始化f，因为f在上一轮可能被处理过，其实不处理也行，反正最后都会依次覆盖的
            la = strlen(a[i] + 1);
            lb = strlen(b + 1);
            for (int j = 1; j <= la; ++j)
                f[j][0] = j; //全部删除就好
            for (int j = 1; j <= lb; ++j)
                f[0][j] = j; //逐个插入就好
            for (int j = 1; j <= la; ++j)
                for (int k = 1; k <= lb; ++k)
                {
                    f[j][k] = min(f[j - 1][k] + 1, f[j][k - 1] + 1); //插入和删除比较
                    if (a[i][j] == b[k])                             //最后一位相同，不用改的情况
                        f[j][k] = min(f[j][k], f[j - 1][k - 1]);
                    else
                        f[j][k] = min(f[j][k], f[j - 1][k - 1] + 1); //最后一位需要修改
                }
            if (f[la][lb] <= l)
                ++res;
        }
        cout << res << endl;
    }
    return 0;
}